package sort.leetcode_1122_easy_costume_sort;

public class CountSortSolution {
    /**
     * 利用计数排序的方式来代替哈希表。
     * 由于arr2中的元素都存在于arr1中，利用一个额外的数组来记录arr1中 对应元素出现的次数
     * 如果arr1 = {2,2,1,4,3,5};
     * 对应的计数数组 = {0,1,2,1,1,1};
     *      对应的索引：0,1,2,3,4,5
     *
     *      意思就是：0出现了0次
     *              1出现了1次
     *              2出现了2次
     *              3出现了1次
     *              4出现了1次
     *              5出现了1次
     *    假设arr2 = { 4, 5, 2, 2};
     *                0, 1, 2, 3
     *    就可以利用计数关系 先用arr2覆盖掉arr1（如代码）
     *
     *    最后处理arr1中的剩余元素。
     */
    //题目给出范围在1-1000，所以可以利用计数排序
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        //利用一个额外数组，记录 位置和次数关系
        int[] count = new int[1001];
        for (int value : arr1) {
            count[value]++;
        }
        int i = 0;
        /*
            将arr2中的元素放入arr1中

            value = 4;           |   value = 5;            |  value = 2;           |   value = 2;
            count[4] = 1 > 0     |   count[5] = 1 > 0      |  count[2] = 2 > 0     |   count[2] = 1 > 0;
            arr1[0++] = 4, i = 1;|   arr1[1++] = 5 , i = 2;|  arr[2++] = 2, i = 3; |   arr[3++] = 2, i = 4;
            count[4]--  = 0      |   count[5]-- = 0;       |  count[2]-- = 1;      |   count[2]-- = 0;
            arr1 = {4,           |   arr1 = {4,5,          |  arr1 = {4,5,2,       |   arr1 = {4,5,2,2};
         */
        for (int value : arr2){
            while(count[value] > 0){
                arr1[i++] = value;
                count[value]--;
            }
        }
        /*
            最后处理arr1中的剩余元素。
         */
        for(int v = 0; v < count.length; v++){
            //v 元素 count[v] v元素出现的次数
            while(count[v] > 0){
                arr1[i++] = v;
                count[v]--;
            }
        }
        return arr1;
    }
}
